
import os

def partition(data, p, r):  
    i = p-1  
    cmp = data[r]  
    for j in range(p,r):  
        if data[j] < cmp:  
            i = i+1  
            if i <> j: data[i],data[j] = data[j],data[i]  
         
    if (i+1) <> r: data[i+1],data[r] = data[r],data[i+1]   
    return i+1  
def randomPartition(data, p, r):  
    import random  
    i = random.randint(p,r)  
    data[i], data[r] = data[r], data[i]  
    return partition(data, p, r)  
      
def quickSort(data, p, r):  
    if p < r:  
        q = partition(data, p, r)   
        #q = randomPartition(data, p, r)  
        quickSort(data, p, q-1)  
        quickSort(data, q+1, r)  